home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / SORTDEMO.ARJ / SDSORT06.INC < prev    next >
Text File  |  1992-04-15  |  3KB  |  82 lines
  1. (*
  2. ╔═══════════════════════════════════════════════════════════════════════════╗
  3. ║ Turbo Pascal 6.0 Include File : SDSORT06.INC                              ║
  4. ╟───────────────────────────────────────────────────────────────────────────╢
  5. ║ Program : SORTDEMO.PAS                                                    ║
  6. ╟───────────────────────────────────────────────────────────────────────────╢
  7. ║ Version : 1.0                                                             ║
  8. ╟───────────────────────────────────────────────────────────────────────────╢
  9. ║ Copyright (c) 1992  by  Jon S. Russell                                    ║
  10. ╟───────────────────────────────────────────────────────────────────────────╢
  11. ║ Quick-Sort #2 routines for SORTDEMO.PAS                                   ║
  12. ╚═══════════════════════════════════════════════════════════════════════════╝
  13.                                                                            *)
  14. procedure QuickSort2 (var Info : InfoType;
  15.                           First : IndexType;
  16.                           Last  : IndexType);
  17. var
  18.   SplitPt1 : IndexType;
  19.   SplitPt2 : IndexType;
  20.  
  21.   (*───────────────────────────────────────────────────────────────────────*)
  22.  
  23.   procedure Split (var Info     : InfoType;
  24.                        First    : IndexType;
  25.                        Last     : IndexType;
  26.                    var SplitPt1 : IndexType;
  27.                    var SplitPt2 : IndexType);
  28.  
  29.     (* Chooses a splitting value and arranges List so that *)
  30.     (* List[First] .. List[SplitPt2] <= SplitVal and       *)
  31.     (* List[SplitPt1+1] .. List[Last] > SplitVal.          *)
  32.  
  33.   var
  34.     SplitVal : ListElemType;
  35.  
  36.   begin  (* Split *)
  37.     (* Let SplitVal be the middle value *)
  38.     SplitVal := Info.List[(First+Last) div 2];
  39.  
  40.     (* Loop Invariant: elements to the left of First are *)
  41.     (* less than or equal to SplitVal;  elements to the  *)
  42.     (* right of Last are greater than SplitVal.          *)
  43.     repeat
  44.       (* Increment First until element > SplitVal. *)
  45.       while Info.List[First].Key < SplitVal.Key do
  46.         inc(First);
  47.  
  48.       (* Decrement Last until element < SplitVal. *)
  49.       while Info.List[Last].Key > SplitVal.Key do
  50.         dec(Last);
  51.  
  52.       (* If First and Last are on the wrong side of the split *)
  53.       (* point, swap the elements and update First and Last.  *)
  54.       if First <= Last then
  55.         begin
  56.           Swap(Info, First, Last);
  57.           inc(First);
  58.           dec(Last);
  59.         end;
  60.     until (First > Last);
  61.  
  62.     SplitPt1 := First;
  63.     SplitPt2 := Last;
  64.   end;   (* Split *)
  65.  
  66.   (*───────────────────────────────────────────────────────────────────────*)
  67.  
  68. begin  (* QuickSort2 *)
  69.   Info.Sorted := false;  (* reset flag *)
  70.  
  71.   if First < Last then
  72.     begin
  73.       Split(Info, First, Last, SplitPt1, SplitPt2);
  74.       if (SplitPt1 < Last) then QuickSort2(Info, SplitPt1, Last);
  75.       if (First < SplitPt2) then QuickSort2(Info, First, SplitPt2);
  76.     end;
  77.  
  78.   Info.Sorted := true;  (* set flag *)
  79. end;   (* QuickSort2 *)
  80.  
  81. (*─────────────────────────────────────────────────────────────────────────*)
  82.